D. GCD-sequence

给定大小为 n 的数组 a

对于 b 数组: bi=GCD(ai,ai+1)1in1

确定是否有可能从数组 a 中删除正好一个数,从而使序列 b 不递减(即 bibi+1 始终为真)。

Example

例如,假设 Khristina 有一个数组 a = [ 20,6,12,3,48,36 ]。如果她从中取出 a4=3 并计算 b 的 GCD 序列,她会得到:

  • b1=GCD(20,6)=2
  • b2=GCD(6,12)=6
  • b3=GCD(12,48)=12
  • b4=GCD(48,36)=12

得到的 GCD 序列 b = [ 2,6,12,12 ]是非递减的,因为 b1b2b3b4 .

无想法

主要思路:

若本来就已经不递减了,这时只需要删除最后一个元素即可保证还是满足的,所以一定是满足条件的

若本来不满足,则一定至少有一个位置满足 gi1>gi ,依次判断在原数组基础上删除 i1,i,i+1 之一是否满足满足条件,只要有满足条件的就可以。

void solve() {
    int n;cin >> n;
    vector<int> a(n), g(n - 1);
    for (int i = 0;i < n;i++)cin >> a[i];
    for (int i = 0;i < n - 1;i++)g[i] = __gcd(a[i], a[i + 1]);
    if (is_sorted(g.begin(), g.end())) {
        cout << "YES\n";return;
    }
    int idx = -1;
    for (int i = 1;i < n - 1;i++) {
        if (g[i - 1] > g[i]) {
            idx = i;
        }
    }
    vector<int> a1(a), a2(a), a3(a);
    a1.erase(a1.begin() + idx - 1);
    a2.erase(a2.begin() + idx);
    a3.erase(a3.begin() + idx + 1);

    vector<int> g1(n - 2), g2(n - 2), g3(n - 2);
    for (int i = 0;i < n - 2;i++) {
        g1[i] = __gcd(a1[i], a1[i + 1]);
        g2[i] = __gcd(a2[i], a2[i + 1]);
        g3[i] = __gcd(a3[i], a3[i + 1]);
    }

    int ok = 0;
    ok += is_sorted(g1.begin(), g1.end());
    ok += is_sorted(g2.begin(), g2.end());
    ok += is_sorted(g3.begin(), g3.end());
    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}